// @algorithm @lc id=313 lang=cpp 
// @title super-ugly-number


#define print(...)
// @test(12,[2,7,13,19])=32
// @test(1,[2,3,5])=1
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> dp(n+1, 1);
        auto const m = primes.size();
        vector<int> nug(m, 1);
        for(int i=2; i<=n; i++){
            vector<int> cug(m, 0);
            for(int j=0; j<m; j++)
                cug[j] = dp[nug[j]] * primes[j];
            dp[i] = *min_element(begin(cug), end(cug));
            for(int j=0; j<m; j++){
                if(dp[i] == cug[j]){
                    nug[j]++;
                    print("dp[", i, "]=", dp[i],
                        ", cug=", Array(cug),
                        ", nug=", Array(nug), "\n")
                }
            }
        }
        return dp[n];
    }
};